package com.base.weeks.weekof271th;

/**
 * 5955. 摘水果
 *
 * 呜呜呜。。
 *
 * @author leon
 * @date 2021年12月12日 12:03
 */
class MaxTotalFruits {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int MAX = 5 * 100000;
        // 计算水果总数前缀和
        int[] sum = new int[MAX];
        int fruitIndex = 0;
        int currentSum = 0;
        for (int i = 0; i < MAX; i++) {
            if (fruitIndex < fruits.length && i == fruits[fruitIndex][0]) {
                currentSum += fruits[fruitIndex][1];
                fruitIndex++;
            }
            sum[i] = currentSum;
        }
        // 计算k步的能走的范围内水果数
        int res = 0;
        // 先往左走i步，再往右走完k-i步
        for (int i = 0; i <= k; i++) {
            int left = Math.max(0, startPos - i);
            int right = Math.min(MAX, left + (k - i));
            int current = sum[right] - (left == 0 ? 0 : sum[left - 1]);
            res = Math.max(res, current);
        }
        // 先往右走i步，再往左走完k-i步
        for (int i = 0; i <= k; i++) {
            int right = startPos + i;
            int left = Math.max(0, right - (k - i));
            int current = sum[right] - (left == 0 ? 0 : sum[left - 1]);
            res = Math.max(res, current);
        }
        return res;
    }
}
